package number_79;

import java.util.Arrays;

/**
 * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *示例:
 *
 * board =
 * [
 *   ['A','B','C','E'],
 *   ['S','F','C','S'],
 *   ['A','D','E','E']
 * ]
 *
 * 给定 word = "ABCCED", 返回 true
 * 给定 word = "SEE", 返回 true
 * 给定 word = "ABCB", 返回 false
 *  
 *
 * 提示：
 *
 * board 和 word 中只包含大写和小写英文字母。
 * 1 <= board.length <= 200
 * 1 <= board[i].length <= 200
 * 1 <= word.length <= 10^3 *  
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-search
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    private boolean[][] isVisited;
    public boolean exist(char[][] board, String word) {
        int rows = board.length, columns = board[0].length;
        isVisited = new boolean[rows][columns];
        int index = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (board[i][j] == word.charAt(0)) {
                    if (isExist(board, i, j, index, word)) {
                        return true;
                    }
                    isVisited = new boolean[rows][columns];
                }
            }
        }
        return false;
    }

    private boolean isExist(char[][] board, int row, int column, int wordIndex, String word) {
        if (row < 0 || row >= board.length || column < 0 ||
                column >= board[0].length ||
                isVisited[row][column]) {
            return false;
        }
        if (wordIndex == word.length() - 1 && board[row][column] == word.charAt(wordIndex)) {
            return true;
        }
        isVisited[row][column] = true;
        boolean exist = false;
        if (board[row][column] != word.charAt(wordIndex)) {
            isVisited[row][column] = false;
            return false;
        }
        exist = isExist(board, row + 1, column, wordIndex + 1, word) ||
        isExist(board, row - 1, column, wordIndex + 1, word) ||
        isExist(board, row, column + 1, wordIndex + 1, word) ||
        isExist(board, row, column - 1, wordIndex + 1, word);
        isVisited[row][column] = false;
        return exist;
    }

    public static void main(String[] args) {
        /*new tree.Solution().exist(new char[][]{{'A', 'B', 'C', 'E'},
                {'S', 'F', 'C', 'S'},
                {'A', 'D', 'E', 'E'}}, "SEE");*/
        new Solution().exist(new char[][]{
                {'a', 'b'}, {'c', 'd'}
        }, "cdba");
    }

}
